#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2e6+7;
const LL MOD = 1e9+7;
LL Fac[MAXN], RFac[MAXN];
LL Fob[MAXN];
LL f[MAXN];
LL Kuai(LL a, LL k) {
    LL ret = 1;
    while (k) {
        if (k&1) {
            ret = (ret * a) % MOD;
        }
        k = (k >> 1);
        a = (a * a) % MOD;
    }
    return ret;
}
void Init() {
    Fac[0] = 1;
    Fac[1] = 1;
    Fob[0] = 0;
    Fob[1] = 1;
    for (int i=2; i<MAXN; ++i) {
        Fac[i] = (Fac[i-1] * i) % MOD;
        Fob[i] = (Fob[i-1] + Fob[i-2]) % (MOD-1);
    }
    RFac[MAXN-1] = Kuai(Fac[MAXN-1], MOD-2);
    for (int i=MAXN-1; i>0; --i) {
        RFac[i-1] = RFac[i] * i % MOD;
    }
}
LL C(LL n, LL k) {
    return Fac[n] * RFac[k] % MOD * RFac[n-k] % MOD;
}
LL getAns(LL g) {
    if (g==0) return 0;
    return (Kuai(2, Fob[g]+MOD-1) + MOD - 1) % MOD;
}
void show(int n) {
    for (int i=0; i<n; ++i) { printf("%d ", Fob[i]); }; printf("\n");
    for (int i=0; i<n; ++i) { printf("%d ", Fac[i]); }; printf("\n");
    for (int i=0; i<n; ++i) { printf("%d ", RFac[i]); }; printf("\n");
}

int main(int argc, char** argv) {
#ifdef hai
    freopen("in.txt", "r", stdin);
#endif
    Init();
//    show(10);
    int T;
    cin>>T;
    LL n,k;
    while (T--) {
        scanf("%lld %lld", &n, &k);
        LL res = 0;
        for (int i=n; i>0; --i) {
            if (n%i==0) {
                LL& t = f[i];
                t = C(n/i+k-1, k-1);
                for (int j=2*i; j<=n; j+=i) {
                    t -= f[j];
                }
                t %= MOD;
                if (t<0) t+= MOD;
            }
            else {
                f[i] = 0;
            }
//            printf("%d : %lld\n", i, f[i]);
            if (f[i]) {
                res = (res + getAns(i)*f[i]) % MOD;
            }
        }
        res = (res * Kuai(C(n+k-1, k-1), MOD-2)) % MOD;
        cout<<res<<endl;
    }
    return 0;
}
